package MyHeap;

import java.util.Arrays;

public class MyHeap implements Operations{
    public int[] element;
    public int usedSize;

    public MyHeap() {
        this.element = new int[10];
    }

    @Override
    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            element[i] = array[i];
            this.usedSize++;
        }
    }

    @Override
    public void creatHeap() {
        for (int parent = (this.usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(parent, this.usedSize);
        }
    }

    @Override
    public void siftDown(int parent, int usedSize) {
        int child = parent * 2 + 1;
        //child指向的元素比child+1的大
        while (child < usedSize) {
            if (child + 1 < usedSize && element[child] < element[child + 1]) {
//                swap(element, child, child + 1);
                child++;
            }
            if (element[parent] < element[child]) {
                swap(element, parent, child);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    //交换两元素
    public void swap(int[] element, int i, int j) {
        int temp = element[i];
        element[i] = element[j];
        element[j] = temp;
    }

    @Override
    public void offer(int val) {
        if (isFull()) {
            expansion();
        }
        element[this.usedSize] = val;
        this.usedSize++;
        siftUp(this.usedSize - 1);
    }

    //判满
    public boolean isFull() {
        return this.usedSize == element.length;
    }

    //扩容
    public void expansion() {
        this.element = Arrays.copyOf(this.element, 2 * this.element.length);
    }

    @Override
    public void siftUp(int child) {
        int parent = (child - 1) / 2;

        while (parent >= 0) {
            if (child + 1 < this.usedSize && element[child] < element[child + 1]) {
                child++;
            }
            if (element[parent] < element[child]) {
                swap(element, parent, child);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    @Override
    public int poll() {
        if (isEmpty()) {
            throw new EmptyHeapException("堆为空，无法取出元素");
        }
        swap(element, 0, this.usedSize - 1);
        int val = element[this.usedSize - 1];
        this.usedSize--;
        siftDown(0, this.usedSize);
        return val;
    }

    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    @Override
    public int peek() {
        if (isEmpty()) {
            throw new EmptyHeapException("堆为空，无法取出元素");
        }
        return element[0];
    }

    public void heapSort() {
        int end = this.usedSize - 1;
        while (end >= 0) {
            swap(element, end, 0);
            siftDown(0, end);
            end--;
        }
    }
}
